For Mixed-Variable Optimization Problem (MVOP) containing both continuous and categorical variables, a coevolution strategy was proposed to search the mixed-variable decision space, and a Coevolutionary Ant Colony Optimization Algorithm for MVOP (CACOA _MV) was developed. In CACOA _MV, the continuous and categorical sub-populations were generated by using the continuous and discrete Ant Colony Optimization (ACO) strategies respectively, the sub-vectors of continuous and categorical variables were evaluated with the help of cooperators, and the continuous and categorical sub-populations were respectively updated to realize the efficient coevolutionary search in the mixed-variable decision space. Furthermore, the ability of global exploration to the categorical variable solution space was improved by introducing a smoothing mechanism of pheromone, and a "best+random cooperators" restart strategy facing the coevolution framework was proposed to enhance the efficiency of coevolutionary search. By comparing with the Mixed-Variable Ant Colony Optimization (ACO _MV) algorithm and the Success History-based Adaptive Differential Evolution algorithm with linear population size reduction and Ant Colony Optimization (L-SHADE _ACO), it is demonstrated that CACOA _MV is able to perform better local exploitation, so as to improve approximation quality of the final results in the target space; the comparison with the set-based Differential Evolution algorithm with Mixed-Variables (DE _MV) shows that CACOA _MV is able to better approximate the global optimal solutions in the decision space and has better global exploration ability. In conclusion, CACOA _MV with the coevolutionary strategy can keep a balance between global exploration and local exploitation, which results in better optimization ability.